\section{Omitted Proofs}

\subsection{Permutation Network}\label{sec:perm-proof}

We now formally prove that the oblivious permutation network protocol in \figureref{fig:switching-net}	and repeated in \figureref{fig:perm-net-repeat} is secure with respect to the  \f{permute} functionality of  \figureref{fig:perm-ideal-2}.

\begin{figure}
	\framebox{\begin{minipage}{0.95\linewidth}\small
			Parameters: $3$ parties denoted as \programmer, \sender and \receiver. Elements are strings in $\Sigma:=\{0,1\}^\sigma$. An input, output vector size of $n, m$.
			\smallskip			
			
			\input{prot-fig-perm}
	\end{minipage}}
	\caption{The Oblivious Permutation Network protocol $\proto{permute}$ repeated. }
	\label{fig:perm-net-repeat}	
\end{figure}

\begin{figure}\small
	\framebox{\begin{minipage}{0.95\linewidth}
			Parameters: $3$ parties denoted as the \programmer, \sender and \receiver. Elements are strings in $\Sigma:=\{0,1\}^\sigma$. An input vector size of $n$ and output size of $m$.
			
			{\bf [Permute]} Upon the command $(\textsc{Permute}, \pi, \shareTwo{A}_0)$ from the \programmer and $(\textsc{Permute}, \shareTwo{A}_1)$ from the \sender:
			\begin{enumerate}
				\item Interpret $\pi: [m]\rightarrow [n]$ as an injective function and $A\in \Sigma^n$. 
				\item Compute $A'\in \Sigma^m$ s.t. $\forall i\in [m], A_{\pi(i)} = A'_i$.
				\item Generate $\shareTwo{A'}$ and send $\shareTwo{A'}_0$ to \programmer and $\shareTwo{A'}_1$ to \receiver.
			\end{enumerate}
	\end{minipage}}
	\caption{The Oblivious Permutation Network ideal functionality \f{permute}.}
	\label{fig:perm-ideal-2}	
\end{figure}

\begin{theorem}\label{thm:permute}
	Protocol $\proto{permute}$ of \figureref{fig:perm-net-repeat} securely realized the ideal functionality \f{permute} of \figureref{fig:perm-ideal-2} given at most one party is corrupted in the semi-honest model.
\end{theorem}
\begin{proof}
	Correctness follows directly from $\pi_1\circ \pi_0 = \pi$ and that the masks cancel out.
	With respect to simulation, consider the following three cases:
	\begin{enumerate}
		\item \emph{Corrupt \programmer}: The view of \programmer contains no messages and therefore is trivial to simulation. 
		\item \emph{Corrupt \sender}:  The view of \programmer contains $\pi_1, S$ which are sent by \programmer. The simulator can uniformly sample $\pi_1:[m]\rightarrow[n]$ from all such injective functions and uniformly sample $S\gets\Sigma^n$. Clearly $S$ has the same distribution.
		
		With respect to $\pi_1$, observe if $\pi_1$ if first fixed uniformly at random then there are exactly $(n-m)!$ ways to choose $\pi_0$. Moreover, for each choice of $\pi_1$ there is a disjoint set of possible $\pi_0$ values. Therefore, \programmer sampling $\pi_0$ uniformly at random results in the distribution of $\pi_1$ also being uniform.
		
		%consider the following hybrid: \programmer first uniformly sample $\pi_1:[m]\rightarrow[n]$ and then defines $\pi_0:[n]\rightarrow[n]$ appropriately. For each choice of $\pi_1$, there are always exactly ${n\choose m}$ options for $\pi_0$. What is more, these options are unique to this choice of $\pi_1$.
		\item \emph{Corrupt \receiver}: The view of \receiver contains $B:= ( A_{\pi_0(1)} \oplus S_1, ..., A_{\pi_0(n)} \oplus S_n)$  and $\pi_1, T\in \Sigma^m$. $\pi_1,T$ are sampled uniformly and therefore trivial to simulation. similarly, each $B_i=A_{\pi_0(i)}\oplus S_i$ where $S_i$ is uniformly distributed in their view. Therefore $B_i$ is similarly distributed. 
	\end{enumerate}
\end{proof}


\subsection{Duplication Network}\label{sec:dup-proof}


We now formally prove that the oblivious duplication network protocol in \figureref{fig:switching-net}	and repeated in \figureref{fig:perm-net-repeat} is secure with respect to the  \f{dup} functionality of  \figureref{fig:dup-ideal-2}.

\begin{figure}
	\framebox{\begin{minipage}{0.95\linewidth}\small
			Parameters: $3$ parties denoted as \programmer, \sender and \receiver. Elements are strings in $\Sigma:=\{0,1\}^\sigma$. An input, output vector size of $n$.
			\smallskip
			
			\input{prot-fig-dup}
	\end{minipage}}
	\caption{The Oblivious Duplication Network protocol \proto{duplicate} repeated. }
	\label{fig:dup-net-repeat}	
\end{figure}


\begin{figure}\small
	\framebox{\begin{minipage}{0.95\linewidth}
			Parameters: $3$ parties denoted as the \programmer, \sender and \receiver. Elements are strings in $\Sigma:=\{0,1\}^\sigma$. An input vector size of $n$ and output size of $n$.
			
			{\bf [Duplicate]} Upon the command $(\textsc{Duplicate}, \pi, \shareTwo{A}_0)$ from the \programmer and $(\textsc{Duplicate}, \shareTwo{A}_1)$ from the \sender:
			\begin{enumerate}
				\item Interpret $\pi: [n]\rightarrow [n]$ as a function s.t. $\pi(1)=1, \pi(i)\in \{i,\pi(i-1)\}$ for $i\in[2,n]$ and $A\in \Sigma^n$. 
				\item Compute $A'\in \Sigma^m$ s.t. $\forall i\in [n], A_{\pi(i)} = A'_i$.
				\item Generate $\shareTwo{A'}$ and send $\shareTwo{A'}_0$ to \programmer and $\shareTwo{A'}_1$ to \receiver.
			\end{enumerate}
	\end{minipage}}
	\caption{The Oblivious Duplication Network ideal functionality \f{duplicate}.}
	\label{fig:dup-ideal-2}	
\end{figure}


\begin{theorem}\label{thm:dup}
	Protocol $\proto{duplicate}$ of \figureref{fig:dup-net-repeat} securely realized the ideal functionality \f{duplicate} of \figureref{fig:dup-ideal-2} given at most one party is corrupted in the semi-honest model.
\end{theorem}
\begin{proof}
	Correctness follows an inductive argument. It is easy to verify $B_1=\shareTwo{A_1}_1$ and that this is correct since $\pi(1)=1$ by definition. Inductively let us assume that ${B_{i-1}}=\shareTwo{A_{\pi(i-1)}}_1$ and we will show that ${B_i}=\shareTwo{A_{\pi(i)}}_1$.  
	Observe that for $i\in[2,n]$
	\begin{align*}
	\shareTwo{B_i}_0&=M^{b_i}_i\qquad\qquad\qquad\qquad\qquad\qquad\qquad\ \ \  \oplus W^{\rho_i}_i\oplus b_i\shareTwo{B_{i-1}}_0 \\
 		    &=\overline{b_i}\shareTwo{A_i}_0\oplus b_i\shareTwo{B_{i-1}}_1 \oplus \shareTwo{B_{i}}_1\oplus W^{b_i\oplus\phi_i}_i\oplus W^{\rho_i}_i\oplus b_i\shareTwo{B_{i-1}}_0  \\
		    &=\overline{b_i}\shareTwo{A_i}_0 \oplus b_i B_{i-1}\oplus \shareTwo{B_i}_1
	\end{align*}
	And therefore $B=\pi(\shareTwo{A}_1)$ and
	
	\begin{align*}
		A'=&\shareTwo{B}_1\oplus R \oplus \pi(\shareTwo{A}_0) \oplus \shareTwo{B}_1\oplus R\\
		=& B \oplus \pi(\shareTwo{A}_0)\\
		=& \pi(\shareTwo{A}_1) \oplus \pi(\shareTwo{A}_0)\\
		=& \pi(A)\\
	\end{align*}
	
	With respect to simulation, consider the following three cases:
	\begin{enumerate}
		\item \emph{Corrupt \programmer}: The transcript of \programmer contains $M^0, M^1\in \Sigma^n,\shareTwo{B_1}_0\in \Sigma, \phi\in \{0,1\}^n$ from \sender and $W^{b_i\oplus\phi_i}_i$ from \receiver. First observe that $\shareTwo{B_1}_0, \phi$ are sampled uniformly and therefore can be simulated as the same. 
		
		 Next recall that
	\begin{align*}	
	M^{b_i}_i=&...\oplus\shareTwo{B_i}_1\\
	M^{\overline{b_i}}_i=&...\oplus W^{\overline{b_i\oplus\phi_i}}_i	
	\end{align*}
	where $\shareTwo{B_i}_1,  W^{\overline{b_i\oplus\phi_i}}_i\in \Sigma$ are sampled uniformly can not in the view of \programmer.  Therefore $M^0_i,M^1_i$ are distributed uniformly.
	
		\item \emph{Corrupt \sender}:  The transcript of \sender contains nothing and therefore is trivial to simulate. Note that the distribution of the output shares in independent of \sender's random tape (view) due to $\programmer,\receiver$ re-randomizing the shares with $R\gets\Sigma^n$.
		
		\item \emph{Corrupt \receiver}:  The transcript of \receiver contains $\shareTwo{B_1}_1, W^0,W^1$ from \sender and $\rho$ from \programmer. $W^0,W^1$ are sampled uniformly and therefore can be simulated as the same. $\shareTwo{B_1}_1=A_1\oplus \shareTwo{B_1}_0$ where $\shareTwo{B_1}_0$ is sampled uniformly and not in the view. Therefore $\shareTwo{B_1}_1$ is distributed uniformly. The same applies to $\rho$ since $\phi$ is uniform and not in the view. 
	\end{enumerate}
\end{proof}




\subsection{Switching Network}\label{sec:switch-proof}


We now formally prove that the oblivious switching network protocol in \figureref{fig:switching-net} and repeated in \figureref{fig:switch-net-repeat} is secure with respect to the  \f{switch} functionality of  \figureref{fig:switch-ideal-2}. In the proof we will replace calls to the Permutaiton and Duplication protocols of \proto{Switch} with their ideal functionalities (\figureref{fig:perm-ideal-2}, \ref{fig:dup-ideal-2}).


\begin{figure}
	\framebox{\begin{minipage}{0.95\linewidth}\small
			Parameters: $3$ parties denoted as \programmer, \sender and \receiver. Elements are strings in $\Sigma:=\{0,1\}^\sigma$. An input, output vector size of $n, m$.
			\smallskip
			
			\input{prot-fig-switch}
	\end{minipage}}
	\caption{The Oblivious Switching Network protocol \proto{switch} repeated. }
	\label{fig:switch-net-repeat}	
\end{figure}

\begin{figure}\small
	\framebox{\begin{minipage}{0.95\linewidth}			
			\input{ideal-fig-switch}
	\end{minipage}}
	\caption{The Oblivious Switching Network ideal functionality \f{switch} repeated.}
	\label{fig:switch-ideal-2}	
\end{figure}



\begin{theorem}\label{thm:switch}
	Protocol $\proto{Switch}$ of \figureref{fig:switch-net-repeat} securely realized the ideal functionality \f{switch} of \figureref{fig:switch-ideal-2} given at most one party is corrupted in the semi-honest  model.
\end{theorem}
\begin{proof}
	Correctness follows from the first oblivious permutation call rearranges the input vector such that each output item which appears $k$ times is followed by $k-1$ items which do not appear in the output. The duplication network then copies each of these output items into the next $k-1$ position. The final permutation places these items in the final order. 
	
	With respect to simulation, the transcript of each party contains their transcripts of three subprotocols: Permute, Shared-Duplicate and Shared-Permute. By \theoremref{thm:permute} the Permute subprotocol transcript can be simulated. Similarly, \theoremref{thm:permute},\ref{thm:dup} also imply that the other two transcripts can be simulated. Therefore this implies that the overall protocol can be simulated given that no other communication is performed. 
		
\end{proof}
%
%
%\subsection{Shared Network}\label{sec:shared-proof}
%
%
%
%\begin{figure}
%	\framebox{\begin{minipage}{0.95\linewidth}\small
%			Parameters: $3$ parties denoted as \programmer, \sender and \receiver. Elements are strings in $\Sigma:=\{0,1\}^\sigma$. An input, output vector size of $n, m$.
%			\smallskip
%			
%			\input{prot-fig-shared}
%	\end{minipage}}
%	\caption{The Oblivious Shared Switching Network protocol \proto{shared} repeated. }
%	\label{fig:shared-net-repeat}	
%\end{figure}
%
%\begin{figure}\small
%	\framebox{\begin{minipage}{0.95\linewidth}
%			
%			Parameters: $3$ parties denoted as the \programmer, \sender and \receiver. Elements are strings in $\Sigma:=\{0,1\}^\sigma$. An input vector size of $n$ and output size of $m$.
%			
%			{\bf [Shared]} Upon the command $(\textsc{Shared}, cmd, \pi, \shareTwo{A}_0)$ from the \programmer and $(\textsc{Shared},cmd, \shareTwo{A}_1)$ from the \sender:
%			\begin{enumerate}
%				\item Interpret $\pi: [m]\rightarrow [n]$ and $A=\shareTwo{A}_0\oplus \shareTwo{A}_1\in \Sigma^n$. 
%				\item If $cmd=\textsc{Permute}$, require $\pi$ to be injective.				
%				\item If $cmd=\textsc{Duplicate}$, require $n=m,\pi(1)=1, \pi(i)\in \{i, \pi(i-1)\}, \forall i\in[2,n]$. 
%				\item Require $cmd\in \{\textsc{Permute},\textsc{Duplicate},\textsc{Switch}\}$.
%
%				\item Compute $A'\in \Sigma^m$ s.t. $\forall i\in [m], A_{\pi(i)} = A'_i$.
%				\item Generate $\shareTwo{A'}$ and send $\shareTwo{A'}_0$ to \programmer and $\shareTwo{A'}_1$ to \receiver.
%				
%			\end{enumerate}
%			
%	\end{minipage}}
%	\caption{The Oblivious Shared Switching Network ideal functionality \f{shared}.}
%	\label{fig:shared-ideal-2}	
%\end{figure}
%
%
%
%\begin{theorem}\label{thm:shared}
%	Protocol $\proto{shared}$ of \figureref{fig:shared-net-repeat} securely realized the ideal functionality \f{shared} of \figureref{fig:shared-ideal-2} given at most one party is corrupted in the semi-honest  model.
%\end{theorem}
%\begin{proof}
%	Correctness follows from the correctness of the underlying subprotocol and that the \programmer can locally apply the mapping function to their own share. Simulation of this protocol is exactly that of the underlying subprotocol along with updating the output as specified. 
%\end{proof}
%




\subsection{Join Protocol}\label{sec:join-proof}



\begin{theorem}\label{thm:join}
	Protocol $\proto{join}$ of \figureref{fig:full_proto} securely realized the ideal functionality \f{join} of \figureref{fig:full_ideal} given at most one party is corrupted in the semi-honest \f{Permute},\f{Switch},\f{encode}-hybrid model with statistical security parameters $\lambda$.
\end{theorem}
\begin{proof}
	First we demonstrate the correctness of the protocol. Recall that the set of non-\null join keys $\{(X_{J_1}||...||X_{J_l})[i] \mid i\in [n]\}$ are all distinct. The same holds true for the $Y$ table. As such, $P_0$ receives $n$ uniformly random values from \f{encode}. As discussed in \ref{sec:encode}, given that these encodings are of length at least $\lambda + 2 \log_2(n)$ bits, then with probability $1-2^{-\lambda}$ all the encodings are distinct.
	
	Recall that $P_1$ then constructs a cuckoo hash table using the encodings $\mathbb{E}_y$. Given that cuckoo hash table is parameterized as described in  \cite{DRRT18}, this succeeds with overwhelming probability, i.e. $1-2^{-\lambda}$.
	
	The correctness of the rest of the protocol is straight forward. The shared table $\share{Y}$ are permuted to form a shared cuckoo hash table $\share{T}$. Based on the encodings  $\mathbb{E}_x$, the shares in the table $T$ are mapped to the corresponding row of $X$. It is easy to verify that if $Y$ has a matching row then it will have been mapped. Finally, \f{mpc} is used to compute the circuit which constructs the output table.
	
	With respect to simulation, consider the following cases:
	\begin{enumerate}
		\item \emph{Corrupt $P_0$}: The transcript of $P_0$ contains the encodings $\mathbb{E}_x$, the output $\shareTwo{\widehat{Y}^l}_0$ from \f{Switch}, and the output of $\f{mpc}$. Given that the inputs to \f{encode} are either set to \null or all distinct values, the output $\mathbb{E}_x$ is uniformly distributed and therefore can be sample as such by the simulator. Similarly, the output of $\f{Switch},\f{mpc}$ are both uniform.
		
		\item \emph{Corrupt $P_1$}:  The transcript of $P_1$ contains the encodings $\mathbb{E}_y$, the output $\shareTwo{\widehat{T}}_1$ from \f{Permute}, the output $\shareTwo{\widehat{Y}^l}_1$ from \f{Switch}, and the output of $\f{mpc}$. All of these are distributed uniformly. The simulation of this transcript follows the same as that of $P_0$.
		
		\item \emph{Corrupt $P_2$}: The transcript of $P_2$ contains the output $\shareTwo{\widehat{T}}_0$ from \f{Permute}, the output $\shareTwo{\widehat{Y}^l}_0$ from \f{Switch}, and the output of $\f{mpc}$. All of these are distributed uniformly. The simulation of this transcript follows the same as that of $P_0$.
	\end{enumerate}
	
\end{proof}

